package william.list;

/**
 * @author ZhangShenao
 * @date 2024/3/8
 * @description <a href="https://leetcode.cn/problems/reverse-linked-list-ii/description/">...</a>
 */
public class Leetcode92_反转链表2 {
    private class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    /**
     * 处理过程:
     * 1. 找到lPre、l、r和rNext这四个节点
     * 2. 切断[l,r]部分链表其余节点的连接
     * 3. 反转以l为头结点的链表,并返回反转后的头节点
     * 4. 修改反转后的节点指针
     * 5. 返回原头结点
     * <p>
     * 时间复杂度O(N) 仅遍历链表一次
     * 空间复杂度O(1)
     */
    public ListNode reverseBetween(ListNode head, int left, int right) {
        //边界条件校验
        if (head == null || left <= 0 || right <= left) {
            return head;
        }

        //借助哑头
        ListNode dummy = new ListNode();
        dummy.next = head;

        //找到lPre、l、r和rNext这四个节点
        ListNode lPre = dummy;
        for (int i = 0; i < left - 1; i++) {
            lPre = lPre.next;
        }
        ListNode l = lPre.next;
        ListNode r = l;
        for (int i = left; i < right; i++) {
            r = r.next;
        }
        ListNode rNext = r.next;

        //切断[l,r]范围内的链表与其余部分链表的连接
        lPre.next = null;
        r.next = null;

        //反转以l为头结点的链表,并返回反转后的头节点
        ListNode reversed = reverse(l);

        //修改反转后的链表指向
        lPre.next = reversed;
        l.next = rNext;

        //返回原头节点
        return dummy.next;
    }

    /**
     * 反转以head为头结点的链表,并返回反转后的链表头结点
     */
    private ListNode reverse(ListNode head) {
        ListNode cur = head;
        ListNode pre = null;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;

            pre = cur;
            cur = next;
        }

        return pre;
    }

}
